// 文件名：deque_undo_redo.cpp
// 目的：利用 std::deque 的头尾裁剪能力实现“有限容量”的撤销/重做记录。
// 模型：
//   - states_：状态序列（0..cursor_ 为有效历史，cursor_ 之后为“未来”）；
//   - cursor_：当前状态索引；
// 行为：
//   - apply(newState)：丢弃 cursor_ 之后的未来分支，追加新状态；若超容量，弹出最旧状态；
//                     注意：若弹出最旧项，所有索引左移 1，因此 cursor_ 保持不变即可指向新末尾；
//                     若未弹出，cursor_ 自增以指向新末尾。
//   - undo/redo：移动 cursor_ 并返回相应状态（可能为空）。
// 复杂度：
//   - apply：O(k)（k 为丢弃的未来数量）+ O(1) 尾插/可能的头删；
//   - undo/redo/current：O(1)。
// 注意事项：
//   - 容量为固定上限；若需要无损历史，可改用外存或压缩存储；
//   - 多线程使用需同步；
//   - 可扩展：在状态较大时存增量（diff）以降低内存。

#include <deque>
#include <string>
#include <optional>
#include <iostream>

class History {
public:
    explicit History(std::size_t capacity)
        : capacity_(capacity) {
        states_.push_back("initial");
        cursor_ = states_.size() - 1; // 指向“initial”
    }

    // 应用新状态：截断未来，尾部压入；若超容量则丢弃最旧项
    void apply(std::string newState) {
        // 丢弃 cursor_ 之后所有未来分支
        states_.erase(states_.begin() + cursor_ + 1, states_.end());
        // 追加新状态
        states_.push_back(std::move(newState));
        if (states_.size() > capacity_) {
            // 超容量：丢弃最旧项，所有索引左移，cursor_ 不变即指向新末尾
            states_.pop_front();
        } else {
            // 未超容量：cursor_ 前进到新末尾
            ++cursor_;
        }
    }

    // 撤销：若可撤销则 cursor_ 左移，并返回撤销后的当前状态
    std::optional<std::string> undo() {
        if (cursor_ == 0) return std::nullopt;
        --cursor_;
        return states_[cursor_];
    }

    // 重做：若有未来状态则 cursor_ 右移，并返回新的当前状态
    std::optional<std::string> redo() {
        if (cursor_ + 1 >= states_.size()) return std::nullopt;
        ++cursor_;
        return states_[cursor_];
    }

    // 当前状态引用
    const std::string& current() const { return states_[cursor_]; }

private:
    std::size_t capacity_;
    std::deque<std::string> states_;
    std::size_t cursor_;
};

int main() {
    History history(5);
    std::cout << "Current: " << history.current() << '\n';

    history.apply("draw line");
    history.apply("fill color");
    std::cout << "Current: " << history.current() << '\n';

    if (auto state = history.undo()) {
        std::cout << "Undo -> " << *state << '\n';
    }

    if (auto state = history.redo()) {
        std::cout << "Redo -> " << *state << '\n';
    }

    history.apply("add text"); // redo 栈被截断
    std::cout << "Current: " << history.current() << '\n';
    return 0;
}